背景 ​

前情提要 ​

打开视频软件，无论是短视频还是所谓的中长视频，后端相关技术的视频总有一个话题很热点——记录连续 n 天登录的用户，相信你大概率刷到过这相关的视频。他会告诉你这时候可以用 redis 的 bitmap 去记录对应的结果，最后用位运算就可以得到对应的结果。在第一次看到的时候，我觉得设计的很精妙，但是我个人设计的系统从来没有实践过这套方案。但是在实习的时候，部门和流量投放有一定的关系，因此，了解到了人群这一业务场景下 Bitmap 的一些应用。

Bitmap 是什么？ ​

前面提到的这个记录连续登录的例子，就是一个很明显的人群圈选的例子。 bitmap 本质上就是一个信息映射成 Bit 的过程，相较于位图，叫做 bit 的映射似乎更加准确，我们可以将一个 userId 的对应索引的布尔值的情况用 bitmap 中的 0 和 1 来表示，比如 id 为 1,2,7,8,9,10 的用户在第一天登录，那么表示为位图就是 1100001111。那么假设有亿级别的用户，我们就只需要维护一个 1 亿位的 bitmap，其大小大概是 12.5 MB，相较于直接将其存成对应的 map，成本相较还是低廉很多的，并且我们的判存，去重和排序就可以通过位运算的形式进行了。 注意这里的排序是指自然排序，在 BitMap 中，由于每个位（bit）的位置固定，并且直接对应于某个特定的数字，因此当你遍历这个 BitMap 时，就已经在按照数字的升序进行操作了。以下是这种排序方式的简要说明：

1. 创建 BitMap：首先，创建一个足够大的 BitMap，以覆盖所有可能的数字。例如，如果数字的范围是从 0 到 1 亿，你就需要一个包含一亿位的 BitMap。
2. 填充 BitMap：遍历所有的数字（如用户 ID），并将对应数字的位置在 BitMap 中标记为 1。比如，如果数字 5 出现了，就将 BitMap 中的第 5 位标记为 1。
3. 排序输出：为了得到排序后的数字列表，你只需遍历整个 BitMap，按顺序检查每一位。每当你遇到标记为 1 的位时，就输出对应的数字。这样，输出的数字自然就是按照升序排列的，因为你是按照 BitMap 的顺序（从最低位到最高位）进行遍历的。

人群中的应用场景 ​

Bitmap 存在的问题 ​

首先是大 key 问题，以人群场景为例，很多 id 都是 long 型，如果真的按照 Redis Bitmap 允许的最大值分层存储，那么势必会产生很多大 key，这是非常危险的，另外 bitmap 过于大了以后，在 setbit 的时候，由于 Redis 的单线程计算，这段时间无法提供其他服务。我们要解决这个问题，就要在编码的时候注意相关的问题，可以在网址 http://www.redis.cn/redis_memory/ 去提前预估内存，尽量少引进对应的问题，实在不行，直接使用 ClickHouse 等的 join 也未尝不可。 还有一个重要的问题是稀疏数据的问题。如果存在的数据量很小，最大值却很大，这个时候用位图反而弄巧成拙，达不到我们想要节省内存的目的，因为 bitmap 的值的大小是由最大值决定的。这个问题我们用 RoaringBitmap 解决了。

RoaringBitmap ​

RoaringBitmap 是一种为满足大规模人群数据存储而设计的高效数据结构。它对传统位图进行了精巧的优化，尤其在处理大数据集时表现出色。

如图所示，我们知道 RoaringBitmap 有如上图所示三种 Container。 当然可以，下面是一个表格，概述了 RoaringBitmap 中三种容器的主要特点和使用场景：

在 Hive 中，我们可以通过开源的 hive-bitmap-udf.jar 工具包轻松地将表数据转换为 RoaringBitMap。该工具包提供了如 to_bitmap 的 UDF 函数，能将用户 ID 列表转为 RoaringBitMap 对象，并以二进制格式存储于 Hive 表内。此外，该包还包含其他实用的 UDF 函数，如 bitmap_count、bitmap_and 和 bitmap_or，便于对 Bitmap 进行多种操作。处理过的 Bitmap 数据可通过 Spark 等大数据处理引擎批量导入到 ClickHouse 表中。由于 ClickHouse 中不存在二进制数据类型，通常使用字符串类型来接收 Hive 中的二进制数据。通过 byteToString 函数，我们可以将 Hive 表中的 bitmap 数据转换为字符串，这一过程涉及将二进制数据转为字节数组（byte[]），再通过 BASE64 编码成字符串。从 ClickHouse 读取的字符串类型的 bitmap 数据可以通过 bytesToBitMap 函数转换回 RoaringBitMap。在内存中，多个 RoaringBitMap 可以直接进行交集、并集和差集操作，从而高效地创建和管理用户群体。

bitmap 杂谈，聊聊布隆过滤器和 HyperLoglog ​

布隆过滤器 ​

除了上面提到的 RoaringBitmap，其实还有很多俩个很常用的基于 bitmap 实现的数据结构。布隆过滤器一种概率型数据结构，用于测试一个元素是否属于一个集合。它不存储元素本身，而是通过哈希函数来检查元素的可能存在，相较于 RoaringBitmap，他用另一种方案解决了稀疏数据的存储问题。他的工作原理如下所示：

1. 初始化：在开始时，布隆过滤器是一个包含 m 位的位数组（bit array），所有位都设置为 0。
2. 添加元素：当添加一个元素到布隆过滤器时，该元素会通过 k 个不同的哈希函数进行哈希处理，产生 k 个数组位置。然后，将这 k 个位置上的位都设置为 1。
3. 查询元素：要检查一个元素是否在集合中，也将该元素通过相同的 k 个哈希函数处理。如果所有对应的位都是 1，布隆过滤器认为该元素可能在集合中（注意这里有假阳性的可能）。如果任何一个位不是 1，那么该元素绝对不在集合中。 当然这个世界上没有银弹，相信大家都能感受到他的缺点：
4. 存在假阳性的情况，也就是说布隆过滤器可能会错误地判断某个不存在的元素为存在于集合中。
5. 传统的布隆过滤器不支持从集合中删除元素，尽管有一些变种（如 Counting Bloom Filter）支持删除，但是不再只用 0 或者 1 也让其空间成本上升。

HyperLogLog ​

HyperLogLog 是一种概率型数据结构，用于高效地估算集合中不同元素的数量（基数）。它是解决大数据环境下基数统计问题的流行工具，特别是在处理非常大的数据集且允许一定误差的情况下。他的工作原理如下所示: HyperLogLog 通过使用哈希函数将集合中的元素映射到一个较大的空间，并根据映射结果来估计基数。其核心思想基于这样一个事实：哈希值的分布是均匀的。

1. 哈希处理：对集合中的每个元素应用哈希函数，生成一个均匀分布的哈希值。
2. 空间划分：HyperLogLog 将哈希值空间划分为多个桶（bucket），每个桶对应哈希值的一部分。
3. 记录最大前导零：对于每个元素的哈希值，HyperLogLog 记录在其二进制表示中从最左侧开始的连续零的最大数量。这个值被用来估计不同元素的数量。
4. 基数估计：最后，HyperLogLog 通过这些桶中的信息，使用概率论的方法来估计整个数据集的基数。